import common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/10/17 16:23
 * @description
 */
public class TLCR153二叉树中和为目标值的路径 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);
        TreeNode node11 = new TreeNode(11);
        TreeNode node7 = new TreeNode(7);
        TreeNode node2 = new TreeNode(2);
        root.left=node4;
        node4.left=node11;
        node11.left=node7;
        node11.right=node2;

        new TLCR153二叉树中和为目标值的路径().pathTarget(root,22);

    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    private int target;

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        this.target = target;
        travel(root, 0);
        return result;
    }

    private void travel(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        //中左右的遍历方式
        sum += root.val;
        path.add(root.val);
        if (sum == target && root.left == null && root.right == null) {
            result.add(new ArrayList<>(path));
        }
        //往左遍历
        travel(root.left, sum);
        //往右遍历
        travel(root.right, sum);
        //回溯
        path.remove(path.size() - 1);
    }
}
